1. Field of the Invention
This invention relates to methods and circuits for detecting errors in coded digital values.
2. Description of Related Art
Digital memory and communication systems use a variety of error correction coding techniques to detect and correct errors which arise during writing, storing, transmitting, or reading digital data. Single byte error correcting-double byte error detecting codes, referred to herein as SbEC-DbED codes where "b" is the number of bits in a byte, are for detection of up to two byte errors and correction of one byte in a data string. Shigeo Kaneda and Eiji Fujiwara, "Single Byte Error Correcting-Double Byte Error Detecting Codes for Memory Systems," IEEE transactions on Computers, Vol. C-31, No. 7, pp 596-602, July 1982 describes an exemplary embodiment of S4EC-D4ED coding and is incorporated by reference herein in its entirety.
S4EC-D4ED codes contain check bits which circuits or software use to locate and correct a single 4-bit byte (nibble) which contains one or more bit errors. An exemplary S4EC-D4ED code converts digital data d0:63! containing 64 data bits d0 to d63 to an 80-bit code x0:79! containing code bits x0 to x79. Code x0:79! is logically divided into four modules of 20 bits. In each module, the first 16 code bits, x0 to x15, x20 to x35, x40 to x55, or x60 to x75, are equal to data bits d0 to d15, d16 to d31, d32 to d47, or d48 to d63, and the last four code bits x16 to x19, x36 to x39, x56 to x59, or x76 to x79 of each module are check bits c0 to c3, c4 to c7, c8 to c11, or c12 to c15.
A coding system using S4EC-D4ED codes generates check bits C from data D before storing or transmitting code X. Equations A.1 in the Appendix show the relations between check bits c0 to c15 and data bits do to d63 for the exemplary embodiment. An error detection-correction system receives code X, detects whether code X contains errors, and if possible, corrects an error.
Multiplying code X and a parity check matrix E generates a syndrome s. If syndrome s is non-zero, code X contains an error. Assuming a single error is present, syndrome s indicates the location of the error and how to correct the error. FIG. 1A shows the parity check matrix H.sub.(80,64) for the exemplary S4EC-D4ED codes. Matrix H.sub.(80,64) is a 16.times.80 matrix; and entries 0, 1, T, T.sup.2, and T.sup.14 in FIG. 1A are the 4.times.4 matrices shown in FIG. 1B. Modulo 2 matrix multiplication of matrix H.sub.(80,64) and a column vector containing bits x0 to x79 generates the sixteen syndrome bits s0 to s15 which software or circuit logic uses to locate and correct a nibble error. To facilitate location of errors, matrix H.sub.(80,64) is logically partitioned into four modules, each module being a 16.times.20 matrix of bits; and syndrome s is partitioned into four nibbles s.sub.0 to s.sub.3. The four modules of matrix H.sub.(80,64) correspond to the four modules of code X.
FIG. 2 shows a partial gate level diagram of a module decoder which locates errors within the first module (bits x0 to x19) of code X. A complete error detection circuit contains four similar module decoders, one for each module. Gates 201 to 205 generate a signal MP0 which indicates whether an error is in the first module of code X. If the only errors in code X are in data bits d0 to d15, syndrome nibbles s.sub.0, s.sub.1, and s.sub.2 are non-zero because the first module of matrix H.sub.(80,64) contains non-zero matrices which are multiplied by d0 to d15 to generate nibbles s.sub.0, s.sub.1, and S.sub.2. However, the last four rows of the first module of matrix H.sub.(80,64) are zero, and nibble S.sub.3 is independent of first module of code X and remains equal to zero when there are no errors in the second, third, or fourth module of code X. AND gate 205 asserts signal MP0 when each of nibbles s.sub.0, s.sub.1, and S.sub.2 contains a non-zero bit and nibble S.sub.3 is zero. This indicates that data bits d0 to d15 contains an error. If only check bits c0 to c3 contain errors, only nibble s.sub.0 is non-zero because only the first four rows of the first module of matrix H contain non-zero values which are multiplied by c0 to c3 when determining syndrome s. If nibble s.sub.0 is non-zero and nibbles s.sub.1, s.sub.2, and S.sub.3 are zero, AND gate 206 asserts a signal MPar0 to indicate an error is in check bits c0 to c3.
If code X contains a single nibble error, then syndrome s satisfies equation 1, EQU s=e.sub.i .multidot.h.sub.j (equation 1)
where e.sub.i is the nibble error in code X, h.sub.i is a set of four columns of matrix H.sub.(80,64), and i is an index which identifies the position of the nibble error in code X. Equation 1 imposes relations between syndrome nibbles s.sub.0 to S.sub.3 which differ depending on which data nibble contains the error. Logic 211 to 218 performs comparisons between nibbles S.sub.0 to S.sub.2 (S.sub.3 is zero if the error is in the first module) to determine which relation is satisfied and determine which nibble (d0:3!, d4:7!, d8:11!, or d12:15!) within the first module of code X contains the error. If signal MP0 is asserted, AND gates 221 to 224 assert one of nibble pointer signals NP0 to NP3 to identify which data nibble (d0:3!, d4:7!, d8:11!, or dl2:15!) contains the error. Syndrome nibble so provides four bits to correct the nibble error in the first module. Four sets 231 to 234 of four AND gates assert bit error pointer signals BEP0:15! to indicate which of the bits in the first module of code X require correction.
The combination of syndrome s being non-zero and none of the nibble pointers signals being asserted indicates a double error in code X. However, this does not correctly indicate all possible multiple errors. Error detection is desired which detects a greater proportion of multiple errors including, data having errors in two, three, or more nibbles which may be in one or more modules.